/**
 * 链队列实现
 * 使用链表实现队列
 */
public class LinkedQueue<T> implements QueueInterface<T> {
    private QueueNode<T> front; // 队首指针
    private QueueNode<T> rear; // 队尾指针
    private int count; // 当前元素个数

    /**
     * 队列节点类
     */
    private static class QueueNode<T> {
        T data;
        QueueNode<T> next;

        QueueNode(T data) {
            this.data = data;
            this.next = null;
        }
    }

    /**
     * 构造函数
     */
    public LinkedQueue() {
        front = null;
        rear = null;
        count = 0;
    }

    @Override
    public boolean enqueue(T item) {
        QueueNode<T> newNode = new QueueNode<>(item);

        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        count++;
        return true;
    }

    @Override
    public T dequeue() {
        if (isEmpty()) {
            System.out.println("队列为空，无法出队");
            return null;
        }

        T item = front.data;
        front = front.next;

        // 如果队列变空，重置rear指针
        if (front == null) {
            rear = null;
        }

        count--;
        return item;
    }

    @Override
    public T front() {
        if (isEmpty()) {
            return null;
        }
        return front.data;
    }

    @Override
    public boolean isEmpty() {
        return front == null;
    }

    @Override
    public int size() {
        return count;
    }

    /**
     * 显示队列内容
     */
    public void display() {
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }

        System.out.print("队列内容: ");
        QueueNode<T> current = front;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}
